#ifndef __CGRAPH_HPP__
#define __CGRAPH_HPP__

#include <iostream>
#include <vector>
#include <assert.h>
#include <cstdlib>
#include <cstring>

using namespace std;

/**
 * @brief 节点
 *
 */
class Node
{
public:
    Node(char data = 0)
    {
        m_data = data;
        m_visited = false;
    }

    Node(const Node &node)
    {
        if (this == &node)
        {
            return;
        }
        *this = node;
    }

    Node &operator=(const Node &node)
    {
        if (this == &node)
        {
            return *this;
        }
        this->m_data = node.m_data;
        this->m_visited = node.m_visited;
        return *this;
    }

    char m_data;
    bool m_visited;
};

/**
 * @brief 边
 *
 */
class Edge
{
public:
    Edge(int nodeIndexA = 0, int nodeIndexB = 0, int weight = 0) : m_NodeIndexA(nodeIndexA),
                                                                   m_NodeIndexB(nodeIndexB),
                                                                   m_Weight(weight),
                                                                   m_Selected(false)
    {
    }

    Edge(const Edge &edge)
    {
        if (this == &edge)
        {
            return;
        }
        *this = edge;
    }

    Edge &operator=(const Edge &edge)
    {
        if (this == &edge)
        {
            return *this;
        }
        this->m_NodeIndexA = edge.m_NodeIndexA;
        this->m_NodeIndexB = edge.m_NodeIndexB;
        this->m_Weight = edge.m_Weight;
        this->m_Selected = edge.m_Selected;
        return *this;
    }

    int m_NodeIndexA;
    int m_NodeIndexB;
    int m_Weight;
    bool m_Selected;
};

/**
 * @brief 图
 *
 */
class Graph
{
public:
    /**
     * @brief Construct a new Graph object
     *
     * @param Capacity
     * @param directed
     */
    Graph(int Capacity, bool directed = false)
    {
        m_Capacity = Capacity;
        m_NodeCount = 0;
        m_NodeArray = new Node[m_Capacity];
        m_Matrix = new int[m_Capacity * m_Capacity];
        memset(m_Matrix, 0, m_Capacity * m_Capacity * sizeof(int));
        m_EdgeArray = new Edge[m_Capacity - 1];
        m_List = new VNode[m_Capacity];
        m_directed = directed;
        if (m_directed == true)
        {
            m_TList = new VNode[m_Capacity];
            outDegree = new vector<int>(m_Capacity, 0);
            inDegree = new vector<int>(m_Capacity, 0);
        }
    }

    /**
     * @brief Destroy the Graph object
     *
     */
    ~Graph(void)
    {
        delete[] m_NodeArray;
        delete[] m_Matrix;
        delete[] m_EdgeArray;
        delete[] m_List;
        if (m_directed)
        {
            delete[] m_TList;
        }
    }

    /**
     * @brief 添加节点
     *
     * @param node
     */
    void addNode(Node *node)
    {
        assert(node);
        m_NodeArray[m_NodeCount].m_data = node->m_data;
        m_NodeCount++;
    }

    /**
     * @brief 重置访问
     *
     */
    void reset()
    {
        for (int i = 0; i < m_NodeCount; i++)
        {
            m_NodeArray[i].m_visited = false;
        }
    }

    /**
     * @brief Set the Value For Directed Graph object
     *
     * @param row 起点
     * @param col 终点
     * @param val 权值
     * @return true 设置成功
     * @return false 设置失败
     */
    bool setValueForDirectedGraph(int row, int col, int val = 1)
    {
        if (row < 0 || row >= m_Capacity)
        {
            return false;
        }
        if (col < 0 || col >= m_Capacity)
        {
            return false;
        }
        m_Matrix[row * m_Capacity + col] = val;
        return true;
    }

    /**
     * @brief Set the Value For Undirected Graph object
     *
     * @param row 起点
     * @param col 终点
     * @param val 权值
     * @return true 设置成功
     * @return false 设置失败
     */
    bool setValueForUndirectedGraph(int row, int col, int val)
    {
        if (row < 0 || row >= m_Capacity)
        {
            return false;
        }
        if (col < 0 || col >= m_Capacity)
        {
            return false;
        }
        m_Matrix[row * m_Capacity + col] = val;
        m_Matrix[col * m_Capacity + row] = val;
        return true;
    }

    /**
     * @brief Get the Value object
     *
     * @param row 起点
     * @param col 终点
     * @param val 权值
     * @return true 获取成功
     * @return false 获取失败
     */
    bool getValue(int row, int col, int &val)
    {
        if (row < 0 || row >= m_Capacity)
        {
            return false;
        }
        if (col < 0 || col >= m_Capacity)
        {
            return false;
        }
        val = m_Matrix[row * m_Capacity + col];
        return true;
    }

    /**
     * @brief 广度优先搜索
     *
     * @param index 起点
     */
    void BFS(int index)
    {
        cout << m_NodeArray[index].m_data << " ";
        m_NodeArray[index].m_visited = true;

        vector<int> cur;
        cur.push_back(index);

        BFSImpl(cur);
    }

    /**
     * @brief 深度优先搜索
     *
     * @param index 起点
     */
    void DFS(int index)
    {
        int val = 0;
        cout << m_NodeArray[index].m_data << " ";
        m_NodeArray[index].m_visited = true;

        for (int i = 0; i < m_Capacity; i++)
        {
            getValue(index, i, val);
            if (val != 0)
            {
                if (m_NodeArray[i].m_visited)
                {
                    continue;
                }
                DFS(i);
            }
            else
            {
                continue;
            }
        }
    }

    /**
     * @brief Get the Matirx object
     *
     * @return int* 邻接矩阵
     */
    int *getMatirx()
    {
        return m_Matrix;
    }

    /**
     * @brief 邻接矩阵转换成邻接表
     *
     */
    void MatToList()
    {
        ANode *cur;
        for (int i = 0; i < m_NodeCount; i++)
        {
            m_List[i].firstarc = nullptr;
        }
        for (int i = 0; i < m_NodeCount; i++)
        {
            for (int j = 0; j < m_NodeCount; i++)
            {
                if (m_Matrix[i * m_Capacity + j] != 0)
                {
                    cur = new ANode;
                    cur->adjvex = j;
                    cur->nextarc = m_List[i].firstarc;
                    m_List->firstarc = cur;
                }
            }
        }
    }

    /**
     * @brief 邻接表转换为逆邻接表
     * 
     */
    void trans()
    {
        for (int i = 0; i < m_Capacity; i++)
        {
            m_TList[i] = m_List[i];
            m_TList[i].firstarc = nullptr;
        }

        for (int i = 0; i < m_Capacity; i++)
        {
            ANode *cur, *p;
            int index;

            cur = m_List[i].firstarc;
            while (cur)
            {
                index = cur->adjvex;
                p = new ANode;
                p->adjvex = i;
                p->weight = cur->weight;
                p->nextarc = m_TList[index].firstarc;
                m_TList[index].firstarc = p;
                cur = cur->nextarc;
            }
        }
    }

    void dispMat()
    {
        for (int i = 0; i < m_Capacity; i++)
        {
            for (int j = 0; j < m_Capacity; j++)
            {
                cout << m_Matrix[i * m_Capacity + j] << " ";
            }
            cout << endl;
        }
    }

    void dispList()
    {
        ANode *cur;
        for (int i = 0; i < m_NodeCount; i++)
        {
            cout << m_NodeArray[i].m_data << " : ";
            cur = m_List->firstarc;
            while (cur != nullptr)
            {
                cout << cur->data << " ";
                cur = cur->nextarc;
            }
            cout << endl;
        }
    }
    
    /**
     * @brief 度的计算
     * 
     */
    void Degree()
    {
        for(int i = 0; i<m_Capacity;i++)
        {
            ANode *cur = m_List[i].firstarc;
            while (cur)
            {
                outDegree[i]++;
                inDegree[cur->adjvex]++;
            }
        }
    }

    /**
     * @brief Get the Out Degree object
     * 
     * @return vector<int> 
     */
    vector<int> getOutDegree()
    {
        return *outDegree;
    }

    /**
     * @brief Get the In Degree object
     * 
     * @return vector<int> 
     */
    vector<int> getInDegree()
    {
        return *inDegree;
    }
private:
    int m_Capacity;
    int m_NodeCount;
    Node *m_NodeArray;
    int *m_Matrix;
    Edge *m_EdgeArray;
    bool m_directed;

    class ANode
    {
    public:
        char data;
        int adjvex;
        int weight;
        ANode *nextarc;
    };

    class VNode
    {
    public:
        char data;
        ANode *firstarc;
    };

    VNode *m_List;
    VNode *m_TList;

    vector<int> *outDegree;
    vector<int> *inDegree;

    /**
     * @brief BFS接口
     *
     * @param pre
     */
    void BFSImpl(vector<int> pre)
    {
        int val = 0;
        vector<int> cur;
        for (int i = 0; i < (int)pre.size(); i++)
        {
            for (int j = 0; j < m_Capacity; j++)
            {
                getValue(pre[i], j, val);
                if (val != 0)
                {
                    if (m_NodeArray[i].m_visited)
                    {
                        continue;
                    }
                    cout << m_NodeArray[j].m_data << " ";
                    m_NodeArray[j].m_visited = true;
                    cur.push_back(j);
                }
                else
                {
                    continue;
                }
            }
        }
        if (cur.empty())
        {
            return;
        }
        else
        {
            BFSImpl(cur);
        }
    }
};

#endif